class Solution
{
public:
    vector<int> minReverseOperations(int n, int p, vector<int> &banned, int k)
    {
        vector<int> answer(n, -1);
        answer[p] = 0;

        queue<int> q;
        q.push(p);

        unordered_set<int> bannedS = {banned.begin(), banned.end()};
        set<int> unvisited;
        for (int i = 0; i < n; ++i)
        {
            if (i == p)
            {
                continue;
            }
            if (bannedS.count(i))
            {
                continue;
            }
            if ((k & 1) && (abs(i - p) & 1))
            {
                continue;
            }
            unvisited.insert(i);
        }

        int opCount = 0;

        auto getFilppedPos = [](int pos, int arrayBegin, int k)
        {
            if (k & 1)
            {
                int arrayMiddle = arrayBegin + k / 2;
                return 2 * arrayMiddle - pos;
            }
            else
            {
                int arrayMiddle2 = 2 * arrayBegin + k - 1;
                return arrayMiddle2 - pos;
            }
        };

        while (!q.empty())
        {
            ++opCount;
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                int pos = q.front();
                q.pop();

                int subArrayMostLeft = max(0, pos - k + 1);
                int posLeftMost = getFilppedPos(pos, subArrayMostLeft, k);
                int subArrayMostRight = min(n - k, pos);
                int posRightMost = getFilppedPos(pos, subArrayMostRight, k);

                unordered_set<int> thisVisit;

                for (auto targetPos = unvisited.lower_bound(posLeftMost); targetPos != unvisited.end(); ++targetPos)
                {
                    if ((*targetPos - posLeftMost) & 1)
                    {
                        continue;
                    }
                    if (*targetPos > posRightMost)
                    {
                        break;
                    }
                    answer[*targetPos] = opCount;
                    thisVisit.insert(*targetPos);
                    q.push(*targetPos);
                }

                for (int visited : thisVisit)
                {
                    unvisited.erase(visited);
                }
            }
        }
        return answer;
    }

    // 直接bfs会超时
    vector<int> minReverseOperations(int n, int p, vector<int> &banned, int k)
    {
        bool stepIsEven = (k & 1);
        unordered_set<int> visited = {banned.begin(), banned.end()};
        vector<int> answer(n, -1);
        answer[p] = 0;

        queue<int> q;
        q.push(p);
        visited.insert(p);

        int opCount = 0;

        auto getFilppedPos = [](int pos, int arrayBegin, int k)
        {
            if (k & 1)
            {
                int arrayMiddle = arrayBegin + k / 2;
                return 2 * arrayMiddle - pos;
            }
            else
            {
                int arrayMiddle2 = 2 * arrayBegin + k - 1;
                return arrayMiddle2 - pos;
            }
        };

        while (!q.empty())
        {
            ++opCount;
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                int pos = q.front();
                q.pop();

                int subArrayMostLeft = max(0, pos - k + 1);
                int posLeftMost = getFilppedPos(pos, subArrayMostLeft, k);
                int subArrayMostRight = min(n - k, pos);
                int posRightMost = getFilppedPos(pos, subArrayMostRight, k);

                for (int targetPos = posLeftMost; targetPos <= posRightMost; targetPos += 2)
                {
                    if (!visited.count(targetPos))
                    {
                        answer[targetPos] = opCount;
                        visited.insert(targetPos);
                        q.push(targetPos);
                    }
                }
            }
        }
        return answer;
    }
};